package summer.presum;

public class Solution304 {
    public int[] statisticalResult(int[] arrayA) {
        if (arrayA.length == 0) return new int[]{};
        int pre = 1;
        int n = arrayA.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = pre;
            pre *= arrayA[i];
        }
        pre = arrayA[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            res[i] *= pre;
            pre *= arrayA[i];
        }
        return res;
    }
}

class NumMatrix {
    int[][] dp;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row2 + 1][col1] - dp[row1][col2 + 1] + dp[row1][col1];
    }
}